package io.github.hadyang.leetcode.random;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
 *
 * <p>示例 1:
 *
 * <p>输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例 2:
 *
 * <p>输入: coins = [2], amount = 3 输出: -1 说明: 你可以认为每种硬币的数量是无限的。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/coin-change
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q322 {
  public int coinChange(int[] coins, int amount) {
    if (coins.length == 0) {
      return -1;
    }

    Arrays.sort(coins);

    int[] count = new int[amount + 1];
    for (int i = 1; i < count.length; i++) {
      int min = Integer.MAX_VALUE;

      for (int coin : coins) {
        if (i - coin < 0) {
          break;
        }

        int preCount = count[i - coin];
        if (preCount == Integer.MAX_VALUE) {
          continue;
        }
        min = Math.min(min, preCount + 1);
      }
      count[i] = min;
    }

    int res = count[amount];
    if (res == Integer.MAX_VALUE) {
      return -1;
    }

    return res;
  }

  @Test
  public void test() {
    Assert.assertEquals(3, coinChange(new int[] {1, 2, 5}, 11));
    Assert.assertEquals(-1, coinChange(new int[] {2}, 3));
    Assert.assertEquals(3, coinChange(new int[] {17, 11, 7}, 29));
    Assert.assertEquals(2, coinChange(new int[] {17, 11, 7}, 24));
    Assert.assertEquals(1, coinChange(new int[] {17, 11, 7}, 7));
    Assert.assertEquals(-1, coinChange(new int[] {17, 11, 7}, 6));
    Assert.assertEquals(4, coinChange(new int[] {1, 2, 5, 10}, 18));
  }
}
